package cetc;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // write your code here
        int[][] books = {{1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}};
         System.out.println("final:"+minHeightShelves(books,4)); //动态规划法

    }


    public static int minHeightShelves(int[][] books, int shelfWidth) {

        int num = books.length;
        if (num == 1) {
            return books[0][1];
        }
        int[] dp = new int[num];
        dp[0] = books[0][1];
        for (int i = 1; i < num; i++) {
            System.out.println("now i is:"+i);
            int height = books[i][1];
            int weight = books[i][0];
            System.out.println("now height="+"books["+i+"][1]" +"is:"+height);
            System.out.println("now weight="+"books["+i+"][0]" +"is:"+weight);
            dp[i] = dp[i - 1] + books[i][1];
            System.out.println("now dp["+i+"] = dp["+i+" - 1] + books["+i+"][1] is:"+dp[i]);
            for (int j = i - 1; j >= 0; j--) {
                System.out.println("loop in j...............................................");
                System.out.println("now j is:"+j);
                height = Math.max(height, books[j][1]);
                weight = weight + books[j][0];
                System.out.println("now height = Math.max(height, books["+j+"][1])  is:"+height);
                System.out.println("now weight = weight + books["+j+"][0] is:"+weight);
                if (weight > shelfWidth) {
                    System.out.println("############break is called!!!!############");
                    break;
                }
                if (j == 0) {
                    dp[i] = Math.min(dp[i], height);
                    System.out.println("j=0 is called now dp[i] = Math.min(dp[i], height):"+dp[i]);
                } else {
                    dp[i] = Math.min(dp[i], dp[j - 1] + height);
                    System.out.println("now dp[i] = Math.min(dp[i], dp[j - 1] + height) is:"+dp[i]);
                }

            }
        }
        for (int i=0;i<dp.length;i++){


        System.out.println("now is print dp["+i+"]= "+dp[i]);
        }
        return dp[num - 1];
    }


}

